﻿namespace Acoris.Document
{
    using System;
    using System.Diagnostics;

    // represents a formated node
    sealed class FormatNode
    {
        internal static readonly FormatNode EmptyNode = new FormatNode
        {
            left = null,
            right = null,
            height = 0,
            content = null,
            length = 0,
            parent = null
        };

        #region Fields

        internal FormatNode parent;
        internal FormatNode left;
        internal FormatNode right;
        internal IContentSegment content;
        internal byte height;
        internal int length;

        #endregion

        internal int Balance {
            get {
                var nullValue = -1;
                return (left?.height ?? nullValue) - (right?.height ?? nullValue);
            }
        }

        #region StoreElement / StoreFormat / ClearFormat / ClearContent / Clone

        /// <summary>
        /// 存储指定内容到当前节点
        /// </summary>
        /// <param name="content">指定要存储的内容</param>
        internal void StoreElements(IContentSegment content)
        {
            Debug.Assert(content != null);
            this.length += content.Length;
            this.content = content;
        }

        /// <summary>
        /// 应用指定的样式到当前节点
        /// </summary>
        /// <param name="format">指定要应用的样式</param>
        internal void StoreFormat(IContentFormat format)
        {
            Debug.Assert(format != null);
            var content = this.content;
            content.ApplyFormat(format);
        }

        /// <summary>
        /// 清除样式
        /// </summary>
        internal void ClearFormat()
        {
            this.content = null;
            this.content.ClearFormat();
        }

        /// <summary>
        /// 清除内容
        /// </summary>
        internal void ClearContent()
        {
            this.content = null;
        }

        internal FormatNode Clone() {
            return new FormatNode
            {
                content = content,
                left = left,
                right = right,
                height = height,
                length = length,
                parent = parent
            };
        }

        #endregion

        #region ReduceElement / Rebalance

        internal void ReduceElement()
        {
            // this method will execute when application delete some content
            // that we should reduce the empty node, after the reduce operation 
            // it need rebalancing.
            // this method doesn't like rope data-structure,it would not be merge in the 
            // normal time.
                        
            if(height == 0) {

                return;
            }
            else if(height == 1) {
                if (left == null && right == null) {
                    height--;
                    return;
                }

                if (left == null) {
                    this.content = right.content;
                    this.length = right.length;
                    this.height--;
                    this.right = null;
                }
                else if (right == null) {
                    this.content = left.content;
                    this.length = left.length;
                    this.left = null;
                    this.height--;
                }
                parent.length = (parent.left?.length ?? 0) + (parent.right?.length ?? 0);
            }
            else {
                if (left != null) {
                    left.ReduceElement();
                }
                if(right != null) {
                    right.ReduceElement();
                }
            }
        }

        internal void Rebalance()
        {
            while (Math.Abs(this.Balance) > 1) {
                if (this.Balance < -1) {
                    RotateLeft();
                }
                else if(this.Balance > 1) {
                    RotateRight();
                }
            }
            ReduceElement();
            this.height = (byte)(1 + Math.Max(left.height, right.height));
        }

        #endregion

        #region RotateLeft / RotateRight

        void RotateLeft()
        {
            /* Rotate tree to the left
			 * 
			 *       this               this
			 *       /  \               /  \
			 *      A   right   ===>  left  C
			 *           / \          / \
			 *          B   C        A   B
			 */
            var a = this.left;
            var left = this.right;
            var b = left.left;
            var c = left.right;

            left.left = a;
            left.right = b;
            this.left = left;
            this.right = c;
            this.height = (byte)(1 + Math.Max(this.left.height, this.right.height));            
        }

        void RotateRight()
        {
            /* Rotate tree to the right
			 * 
			 *       this             this
			 *       /  \             /  \
			 *     left  C   ===>    A  right
			 *     / \                   /  \
			 *    A   B                 B    C
			 */
            var right = this.left;
            var a = right.left;
            var b = right.right;
            var c = this.right;

            right.left = b;
            right.right = c;

            this.left = a;
            this.right = right;
            this.height = (byte)(1 + Math.Max(this.left.height, this.right.height));
        }

        #endregion

        #region Split / Insert /InsertRange / RemoveRange / Concat

        //
        internal FormatNode Split(int offset)
        {
            Debug.Assert(offset < this.length);
            Debug.Assert(content is TextSegment);

            if(height == 0) {
                var splitAfter = content.Split(offset);
                if(splitAfter == null) {
                    return EmptyNode;
                }
                return new FormatNode
                {
                    content = splitAfter,
                    length = splitAfter.Length,
                    height = 0
                };
            }
            else {
                if (offset < this.left.length) {
                    return this.left.Split(offset);
                }
                else {
                    return this.right.Split(offset - this.left.length);
                }
            }
        }

        //
        internal FormatNode Insert(int offset,FormatNode node)
        {
            Debug.Assert(length > offset);

            if(height == 0) {
                /*
                 *       parent                     parent
                 *     /        \       =>        /       \
                 *   this         B             result      B
                 *                             /      \
                 *                           this     Node
                 */                          
                var result = Clone();
                result.left = this;
                this.parent = result;

                result.right = node;
                node.parent = result;

                result.content = null;
                result.height = (byte)(1 + Math.Max(result.left.height, result.right.height));
                result.length = result.left.length + result.right.length;

                return result;
            }
            else {
                if (offset < left.length) {
                    return left = left.Insert(offset, node);
                }
                else{
                    return right = right.Insert(offset - left.length, node);
                }
            }
        }

        //
        internal FormatNode Remove(int offset)
        {
            Debug.Assert(offset > length);
            if(height == 0) {
                return this;
            }
            else {
                if(offset < left.length) {
                    return left.Remove(offset);
                }
                else if(right != null) {
                    return right.Remove(offset - left.length);
                }
            }
            return null;
        }

        internal static FormatNode Concat(FormatNode left,FormatNode right)
        {
            if(left == null) {
                return right;
            }

            if(right == null) {
                return left;
            }

            return new FormatNode
            {
                left = left,
                right = right,
                height = (byte)(1 + Math.Max(left.height, right.height)),
                length = left.length + right.length
            };
        }

        #endregion

        #region IndexOf / Override

        internal FormatNode IndexOf(int offset)
        {
            if(height == 0) {
                return this;
            }
            else {
                if(this.left.length > offset) {
                    return this.left.IndexOf(offset);
                }
                else {
                    return this.right.IndexOf(offset - this.left.length);
                }
            }
        }

        public override string ToString()
        {
            return $"count:{length},height:{height}";
        }

        #endregion
    }

    /// <summary>
    /// 表示一棵文档树
    /// </summary>
    sealed class DocumentTree
    {
        internal FormatNode root = FormatNode.EmptyNode;
    }
}
